'''
Created on Nov 10, 2013

@author: root
'''
import unittest
import colecciones.DefinicionDeGrafo.grafo
import colecciones.Heap.heap
import verticeDistanciado
import colecciones.pila
'''
Clase GrafoDijkstrado: Implementa un dijkstra en un metodo
'''
class GrafoDijkstrado(colecciones.DefinicionDeGrafo.grafo.Grafo):
    
    def __init__(self):
        colecciones.DefinicionDeGrafo.grafo.Grafo.__init__(self)
        self.__dijk_tab__=colecciones.listaEnlazada.ListaEnlazada()
    
    def __set_Dijk_Tab__(self,unVertice):
        '''
        actualiza una tabla de dijktra segun unVertice como origen
        '''
        if unVertice is None:
            self.__dijk_tab__=colecciones.listaEnlazada.ListaEnlazada()
        else:
            rec=self.getListaDeVertices().recorredor()
            rec.comenzar()
            while not rec.fin():
                elem=rec.elemento()
                if(elem is unVertice): 
                    self.__dijk_tab__.agregar([0,None,False],self.__dijk_tab__.getTamanio())
                else:
                    self.__dijk_tab__.agregar([None,None,False],self.__dijk_tab__.getTamanio())
                rec.proximo()
            
    
    def __get_Dijk_Tab__(self):
        '''
        retorna una tabla de dijktra actual
        '''
        return self.__dijk_tab__
    
    def __actualizacionDijkstra__(self,esCostoMaximo):
        '''
        actualiza __dijks_tab__ segun el vertice destino
        '''
        inicial=self.__get_Dijk_Tab__().recorredor()
        inicial.comenzar()
        pos=i=0
        while not inicial.fin():
            if(inicial.elemento()[0]==0):pos=i
            inicial.proximo()
            i+=1
        self.__recDijkstra__(self.vertice(pos),esCostoMaximo)
        
    def __recDijkstra__(self,origen,esCostoMaximo):
        heapAdy=colecciones.Heap.heap.Heap(esCostoMaximo)
        heapAdy.agregar(verticeDistanciado.VerticeDistanciado(
              origen,self.__dijk_tab__.elemento(origen.getPosicion())[0]))
#        print heapAdy
        while not heapAdy.esVacia():
            u=heapAdy.eliminar()
            self.__dijk_tab__.elemento(u.getVertice().getPosicion())[2]=True
#            print self.__dijk_tab__
            rec=u.getVertice().getListaDeAdyacentes().recorredor()
            rec.comenzar()
            while not rec.fin():
                arist_v=rec.elemento() 
#                print arist_v
                if (self.__dijk_tab__.elemento(arist_v.getVerticeDestino().getPosicion())==[None,None,False])|(
                          self.__dijk_tab__.elemento(arist_v.getVerticeDestino().getPosicion())[0]>u.getDistanciAlorigen()+arist_v.getPeso()):
                    self.__dijk_tab__.elemento(arist_v.getVerticeDestino().getPosicion())[0]=u.getDistanciAlorigen()+arist_v.getPeso()
                    self.__dijk_tab__.elemento(arist_v.getVerticeDestino().getPosicion())[1]=u.getVertice().getPosicion()
#                print self.__dijk_tab__
                if self.__dijk_tab__.elemento(arist_v.getVerticeDestino().getPosicion())[2]==False:
#                    print arist_v.getVerticeDestino()
                    heapAdy.agregar(verticeDistanciado.VerticeDistanciado(
                                      arist_v.getVerticeDestino(),
                                      self.__dijk_tab__.elemento(arist_v.getVerticeDestino().getPosicion())[0]
                                      ))
#                print heapAdy
                rec.proximo()
                
    def __caminosDijkstraDDe__(self,unVertice):
        self.__set_Dijk_Tab__(unVertice)    
        self.__actualizacionDijkstra__(False)
        recTab=self.__dijk_tab__.recorredor()
        recTab.comenzar()
        l=colecciones.listaEnlazada.ListaEnlazada()
        i=0
        while not recTab.fin():
            l.agregar(colecciones.pila.Pila(),l.getTamanio())
#             l.elemento(i).agregar(unVertice.getPosicion(),l.elemento(i).getTamanio())
            elem=recTab.elemento()
            aux=elem[1] 
            while aux!=None:
                l.elemento(i).poner(aux)
                aux=self.__dijk_tab__.elemento(aux)[1]
            i+=1
            recTab.proximo()
        return l
            
            
    def __str__(self,unVertice):
        texto=""
        recCam=self.__caminosDijkstraDDe__(unVertice).recorredor()
        recCam.comenzar()
        i=0
        while not recCam.fin():
            texto+="Camino desde "
            texto+=unVertice.getPosicion().__str__()
            texto+=" hasta "
            texto+=i.__str__()
            texto+=": "
            while not recCam.elemento().esVacia():
                texto+=recCam.elemento().sacar().__str__()
                texto+=", "
            texto+=i.__str__()
            texto+=" costo="
            texto+=self.__dijk_tab__.elemento(i)[0].__str__()
            texto+="\r\n"
            i+=1
            recCam.proximo()
        return texto
        


class Test(unittest.TestCase):


    def testInit(self):
        self.assertIsInstance(GrafoDijkstrado(), GrafoDijkstrado,"Verifica inicializacion")
        grafo=GrafoDijkstrado()
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(0,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(2), 1)# 0 con 2 peso1
        grafo.conectar(grafo.vertice(1), grafo.vertice(0), 3)# 1 con 0 peso3
        grafo.conectar(grafo.vertice(1), grafo.vertice(2), 2)# 1 con 2 peso2
        grafo.conectar(grafo.vertice(1), grafo.vertice(3), 4)# 1 con 3 peso4
        grafo.conectar(grafo.vertice(2), grafo.vertice(3), 7)# 2 con 3 peso7
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 4)# 2 con 4 peso4
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 3)# 3 con 4 peso3
        grafo.conectar(grafo.vertice(3), grafo.vertice(0), 1)# 3 con 0 peso1
        grafo.conectar(grafo.vertice(4), grafo.vertice(0), 6)# 4 con 0 peso6
        grafo.conectar(grafo.vertice(4), grafo.vertice(1), 2)# 4 con 1 peso2
        grafo.conectar(grafo.vertice(4), grafo.vertice(3), 2)# 4 con 3 peso2
        self.assertIsInstance(grafo, GrafoDijkstrado,"Verifica inicializacion")
#         print grafo.__str__(grafo.vertice(2))


    def testSetDijksTab(self):
        grafo=GrafoDijkstrado()
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(0,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(2), 1)# 0 con 2 peso1
        grafo.conectar(grafo.vertice(1), grafo.vertice(0), 3)# 1 con 0 peso3
        grafo.conectar(grafo.vertice(1), grafo.vertice(2), 2)# 1 con 2 peso2
        grafo.conectar(grafo.vertice(1), grafo.vertice(3), 4)# 1 con 3 peso4
        grafo.conectar(grafo.vertice(2), grafo.vertice(3), 7)# 2 con 3 peso7
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 4)# 2 con 4 peso4
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 3)# 3 con 4 peso3
        grafo.conectar(grafo.vertice(3), grafo.vertice(0), 1)# 3 con 0 peso1
        grafo.conectar(grafo.vertice(4), grafo.vertice(0), 6)# 4 con 0 peso6
        grafo.conectar(grafo.vertice(4), grafo.vertice(1), 2)# 4 con 1 peso2
        grafo.conectar(grafo.vertice(4), grafo.vertice(3), 2)# 4 con 3 peso2
        grafo.__set_Dijk_Tab__(grafo.vertice(2))
#         print grafo.__dijk_tab__
        self.assertEquals(grafo.__dijk_tab__.elemento(0), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(1), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(2), [0,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(3), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(4), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        grafo.__set_Dijk_Tab__(None)
        self.assertTrue(grafo.__dijk_tab__.esVacia(), "Verifica tabla borrada")
        grafo.__set_Dijk_Tab__(grafo.vertice(0))
        self.assertEquals(grafo.__dijk_tab__.elemento(0), [0,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(1), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(2), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(3), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(4), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        grafo.__set_Dijk_Tab__(None)
        self.assertTrue(grafo.__dijk_tab__.esVacia(), "Verifica tabla borrada")
        grafo.__set_Dijk_Tab__(grafo.vertice(4))
        self.assertEquals(grafo.__dijk_tab__.elemento(0), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(1), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(2), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(3), [None,None,False], "Verifica correcta inicianizacion de tabla dijkstra")
        self.assertEquals(grafo.__dijk_tab__.elemento(4), [0,None,False], "Verifica correcta inicianizacion de tabla dijkstra")

    def testGetDijksTab(self):
        grafo=GrafoDijkstrado()
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(0,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(2), 1)# 0 con 2 peso1
        grafo.conectar(grafo.vertice(1), grafo.vertice(0), 3)# 1 con 0 peso3
        grafo.conectar(grafo.vertice(1), grafo.vertice(2), 2)# 1 con 2 peso2
        grafo.conectar(grafo.vertice(1), grafo.vertice(3), 4)# 1 con 3 peso4
        grafo.conectar(grafo.vertice(2), grafo.vertice(3), 7)# 2 con 3 peso7
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 4)# 2 con 4 peso4
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 3)# 3 con 4 peso3
        grafo.conectar(grafo.vertice(3), grafo.vertice(0), 1)# 3 con 0 peso1
        grafo.conectar(grafo.vertice(4), grafo.vertice(0), 6)# 4 con 0 peso6
        grafo.conectar(grafo.vertice(4), grafo.vertice(1), 2)# 4 con 1 peso2
        grafo.conectar(grafo.vertice(4), grafo.vertice(3), 2)# 4 con 3 peso2
        grafo.__set_Dijk_Tab__(grafo.vertice(4))
#         print grafo.__get_Dijk_Tab__()
        self.assertEquals(grafo.__get_Dijk_Tab__().elemento(0), [None,None,False],"Verifica funcion que devuelve tab dijkstra")
        self.assertEquals(grafo.__get_Dijk_Tab__().elemento(1), [None,None,False],"Verifica funcion que devuelve tab dijkstra")
        self.assertEquals(grafo.__get_Dijk_Tab__().elemento(2), [None,None,False],"Verifica funcion que devuelve tab dijkstra")
        self.assertEquals(grafo.__get_Dijk_Tab__().elemento(3), [None,None,False],"Verifica funcion que devuelve tab dijkstra")
        self.assertEquals(grafo.__get_Dijk_Tab__().elemento(4), [0,None,False],"Verifica funcion que devuelve tab dijkstra")
        
    def testActualizDijkstra(self):
        grafo=GrafoDijkstrado()
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(0,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(2), 1)# 0 con 2 peso1
        grafo.conectar(grafo.vertice(1), grafo.vertice(0), 3)# 1 con 0 peso3
        grafo.conectar(grafo.vertice(1), grafo.vertice(2), 2)# 1 con 2 peso2
        grafo.conectar(grafo.vertice(1), grafo.vertice(3), 4)# 1 con 3 peso4
        grafo.conectar(grafo.vertice(2), grafo.vertice(3), 7)# 2 con 3 peso7
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 4)# 2 con 4 peso4
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 3)# 3 con 4 peso3
        grafo.conectar(grafo.vertice(3), grafo.vertice(0), 1)# 3 con 0 peso1
        grafo.conectar(grafo.vertice(4), grafo.vertice(0), 6)# 4 con 0 peso6
        grafo.conectar(grafo.vertice(4), grafo.vertice(1), 2)# 4 con 1 peso2
        grafo.conectar(grafo.vertice(4), grafo.vertice(3), 2)# 4 con 3 peso2
        print grafo.vertice(0).getListaDeAdyacentes()
        print grafo.vertice(1).getListaDeAdyacentes()
        print grafo.vertice(2).getListaDeAdyacentes()
        print grafo.vertice(3).getListaDeAdyacentes()
        print grafo.vertice(4).getListaDeAdyacentes()
        grafo.__set_Dijk_Tab__(grafo.vertice(0))
        print grafo.__get_Dijk_Tab__()
        grafo.__actualizacionDijkstra__(False)
        print grafo.__get_Dijk_Tab__()

    def testPrint(self):
        grafo=GrafoDijkstrado()
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(0,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                            )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(1,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(2,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(3,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.agregarVertice(
                 colecciones.DefinicionDeGrafo.vertice.Vertice(4,
                          colecciones.listaEnlazada.ListaEnlazada()
                                    )
                          )
        grafo.conectar(grafo.vertice(0), grafo.vertice(2), 1)# 0 con 2 peso1
        grafo.conectar(grafo.vertice(1), grafo.vertice(0), 3)# 1 con 0 peso3
        grafo.conectar(grafo.vertice(1), grafo.vertice(2), 2)# 1 con 2 peso2
        grafo.conectar(grafo.vertice(1), grafo.vertice(3), 4)# 1 con 3 peso4
        grafo.conectar(grafo.vertice(2), grafo.vertice(3), 7)# 2 con 3 peso7
        grafo.conectar(grafo.vertice(2), grafo.vertice(4), 4)# 2 con 4 peso4
        grafo.conectar(grafo.vertice(3), grafo.vertice(4), 3)# 3 con 4 peso3
        grafo.conectar(grafo.vertice(3), grafo.vertice(0), 1)# 3 con 0 peso1
        grafo.conectar(grafo.vertice(4), grafo.vertice(0), 6)# 4 con 0 peso6
        grafo.conectar(grafo.vertice(4), grafo.vertice(1), 2)# 4 con 1 peso2
        grafo.conectar(grafo.vertice(4), grafo.vertice(3), 2)# 4 con 3 peso2
        print grafo.__str__(grafo.vertice(4))
        

if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']
    unittest.main()